package com.congee02.bt.dfs.top2bottom;

import com.congee02.bt.TreeNode;

public class SmallestFromLeaf {

    public String smallestFromLeaf(TreeNode root) {

        help(root, new StringBuilder());

        return ans;
    }

    String ans = null;
    private void help(TreeNode root, StringBuilder path) {

        if (root == null) {
            return;
        }

        path.append((char) ('a' + root.val));

        if (root.left == null && root.right == null) {
            path.reverse();
            String cur = path.toString();
            path.reverse();
            if (ans == null) {
                ans = cur;
            } else if (cur.compareTo(ans) < 0) {
                ans = cur;
            }
        } else {
            help(root.left, path);
            help(root.right, path);
        }

        path.deleteCharAt(path.length() - 1);
    }

}
